package A_review.review6_28;

import listNodePractice.ListNode;

import java.util.PriorityQueue;

public class ListNodeTest {

//合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//        虚拟头节点 需要两个指针指向  一个一直指向虚拟节点   一个用来当游标移动由虚拟节点组成的链表
        ListNode p = new ListNode(-1);
        ListNode dumpy=p;
        while (list1!=null&&list2!=null){
            if (list1.val< list2.val){
                dumpy.next=list1;
                list1=list1.next;
            }else{
                dumpy.next=list2;
                list2=list2.next;
            }
            dumpy=dumpy.next;
        }
        while (list1!=null){
            dumpy.next=list1;
            list1=list1.next;
            dumpy=dumpy.next;
        }

        while (list2!=null){
            dumpy.next=list2;
            list2=list2.next;
            dumpy=dumpy.next;
        }
        return   p.next;
    }

//    合并k个有序链表

    public ListNode mergeKLists(ListNode[] lists) {

        ListNode dumpy = new ListNode(-1);
        ListNode q=dumpy;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
                lists.length, (a, b)->(a.val - b.val));
        for (ListNode p:lists) {
//            todo:缺少了这个判断条件
            if (p!=null){
                pq.add(p);
            }
        }
        while (!pq.isEmpty()){
            ListNode poll = pq.poll();
            q.next=poll;
            q=q.next;
//            todo： 这里不对    while 应变为if
//            while (poll.next!=null){
                if (poll.next!=null){
                    pq.add(poll.next);
            }
        }
        return  dumpy.next;
    }


//   删除单链表的倒数第k个节点
public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head==null){
            return  null;
        }
        ListNode p1=head;
        ListNode p2=head;
    int m=n;

    while (m>0&&p1!=null){
        p1=p1.next;
        m--;
    }
    ListNode pre=p2;
    //todo: 缺少这种情况
    if(p1==null){
        return head.next;

    }
    while (p1!=null){
        pre=p2;
        p2=p2.next;
        p1=p1.next;
    }
    pre.next=p2.next;
return  head;
}






//找出单链表的中点

    public  ListNode  mid(ListNode head){
        ListNode  slow=head,fast=head;
        while (fast!=null&&fast.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return   slow;

    }


//判断单链表是否存在环


    public  boolean judgeIfCircle(ListNode head){
        ListNode  slow=head,fast=head;
        while (fast!=null&&fast.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow==fast){
                return  true;
            }
        }
        return   false;
    }


//找出单链表环的位置
    public  ListNode findCirclePosition(ListNode head){
        ListNode  slow=head,fast=head;
        while (fast!=null&&fast.next!=null) {
            //todo:  首先找到相遇的位置
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
//            todo:说明无环
            if (fast == null || fast.next == null) {
                return null;
            }
        }
            slow=head;
            while (slow!=fast){
                slow=slow.next;
                fast=fast.next;
            }

        return  slow;
    }








    public static void main(String[] args) {
        ListNodeTest listNodeTest = new ListNodeTest();

        ListNode listNode1 = new ListNode(1);
        ListNode listNode2= new ListNode(6);
        listNode1.next=listNode2;

        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(9);
        listNode3.next=listNode4;

        ListNode listNode = listNodeTest.mergeTwoLists(listNode1, listNode3);
        while (listNode!=null){
            System.out.println(listNode.val);
            listNode=listNode.next;
        }


    }

}
